"""
二分法猜平方根，快速收敛
"""

# todo fixme
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        """
        依次累乘
        """
        if not x:
            return 0
        if x < 4:
            return 1

        l = 1
        r = (x + 1) // 2
        mid = (l + r) // 2

        while l < r:
            q = mid * mid
            """
            大的话可以就减一
            """
            if q > x:
                r = mid - 1
            elif q == x:
                return mid

            else:
                l = mid
            mid = (l + r + 1) // 2

        return l


print(Solution().mySqrt(4))
